from typing import List


class Solution:
    """
    . 平地
    # 障碍物
    S 恶魔出生点
    P 瞬移点
    C 城堡
    """

    _INF = 100001

    def guardCastle(self, grid: List[str]) -> int:
        # ---------- 处理第1种情况 ----------
        # 策略1：将瞬移点视为小恶魔，防御所有小恶魔和瞬移点靠近城堡
        grid1 = [grid[0].replace("P", "S"), grid[1].replace("P", "S")]
        ans1 = self.count(grid1)

        # ---------- 处理第2种情况 ----------
        # 策略2：将瞬移点视为城堡，防御所有小恶魔靠近城堡和瞬移点
        grid2 = [grid[0].replace("P", "C"), grid[1].replace("P", "C")]
        ans2 = self.count(grid2)

        ans = min(ans1, ans2)
        return ans if ans < self._INF else -1

    def count(self, grid: List[str]):
        """计算只考虑小恶魔和城堡的情况"""
        n = len(grid[0])

        # 初始化状态矩阵（与左侧的小恶魔/城堡是否相连）
        # dp[0] = 上方、下方都不相连 : 当左侧为小恶魔时，上方下方都安全；当左侧为城堡上，上方下方都不需要保护
        # dp[1] = 上方不相连、下方相连 : 当左侧为小恶魔时，上方安全，下方不安全；当左侧为城堡上，上方不需要保护，下方需要保护
        # dp[2] = 上方相连、下方不相连 : 当左侧为小恶魔时，上方不安全，下方安全；当左侧为城堡上，上方需要保护，下方不需要保护
        # dp[3] = 上方、下方都相连 : 当左侧为小恶魔时，下方下方都不安全；当左侧为城堡上，上方下方都需要保护
        dp = [0, 0, 0, 0]

        # 初始化左侧角色
        # None = 没有角色
        # 0 = 小恶魔
        # 1 = 城堡
        last_stat = None

        for i in range(n):
            # 当前列包含小恶魔和城堡 -> 防守注定失败
            if "S" in (grid[0][i], grid[1][i]) and "C" in (grid[0][i], grid[1][i]):
                dp[3] = self._INF
                break

            # 当前列包含小恶魔 -> 标记当前角色
            elif "S" in (grid[0][i], grid[1][i]):
                stat = 0
                target = "S"

            # 当前列包含城堡 -> 标记当前角色
            elif "C" in (grid[0][i], grid[1][i]):
                stat = 1
                target = "C"

            # 当前列不包含小恶魔或城堡 -> 标记当前角色
            else:
                stat = None
                target = None

            # 当前列上下均为当前角色：若与之前角色不同，则必须与之前完全分隔
            if (grid[0][i], grid[1][i]) == (target, target):
                if last_stat == 1 - stat:
                    dp = [self._INF, self._INF, self._INF, dp[0]]
                else:
                    dp = [self._INF, self._INF, self._INF, dp[3]]

            # 当前列上方为当前角色，下方为障碍物
            elif (grid[0][i], grid[1][i]) == (target, "#"):
                if last_stat == 1 - stat:
                    dp = [self._INF, self._INF, dp[1], dp[1]]
                else:
                    dp = [self._INF, self._INF, dp[3], dp[3]]

            # 当前列上方为障碍物，下方为当前角色
            elif (grid[0][i], grid[1][i]) == ("#", target):
                if last_stat == 1 - stat:
                    dp = [self._INF, dp[2], self._INF, dp[2]]
                else:
                    dp = [self._INF, dp[3], self._INF, dp[3]]

            # 当前列上方为当前角色，下方为空地
            elif (grid[0][i], grid[1][i]) == (target, "."):
                if last_stat == 1 - stat:
                    dp = [self._INF, self._INF, dp[1] + 1, dp[0]]
                    dp[3] = min(dp[2], dp[3])
                else:
                    dp = [self._INF, self._INF, dp[3] + 1, dp[3]]

            # 当前列上方为空地，下方为当前角色
            elif (grid[0][i], grid[1][i]) == (".", target):
                if last_stat == 1 - stat:
                    dp = [self._INF, dp[2] + 1, self._INF, dp[0]]
                    dp[3] = min(dp[1], dp[3])
                else:
                    dp = [self._INF, dp[3] + 1, self._INF, dp[3]]

            # 当前列上下均为空地
            elif (grid[0][i], grid[1][i]) == (".", "."):
                dp[0] = min(dp[0], dp[1] + 1, dp[2] + 1, dp[3] + 2)
                dp[1] = dp[2] = min(dp[0], dp[3] + 1)

            # 当前列上方为空地，下方为障碍物
            elif (grid[0][i], grid[1][i]) == (".", "#"):
                dp[0] = dp[1] = min(dp[1], dp[3] + 1)
                dp[2] = dp[3]

            # 当前列上方为障碍物，下方为空地
            elif (grid[0][i], grid[1][i]) == ("#", "."):
                dp[0] = dp[2] = min(dp[2], dp[3] + 1)
                dp[1] = dp[3]

            # 当前列上下方均为障碍物
            else:
                dp[0] = dp[1] = dp[2] = dp[3]

            # 如果当前角色不为空，则更改左侧角色
            if stat is not None:
                last_stat = stat

        return dp[3]


if __name__ == "__main__":
    # 3
    print(Solution().guardCastle(grid=["S.C.P#P.",
                                       ".....#.S"]))

    # -1
    print(Solution().guardCastle(grid=["SP#P..P#PC#.S",
                                       "..#P..P####.#"]))

    # 0
    print(Solution().guardCastle(grid=["SP#.C.#PS",
                                       "P.#...#.P"]))

    # 4
    print(Solution().guardCastle(grid=["CP.#.P.",
                                       "...S..S"]))
